#include <iostream>
using namespace std;
enum Colour
{
    RED,
    BLACK
};

template <class K, class V>
struct RBTreeNode
{
    RBTreeNode<K, V> *_left;
    RBTreeNode<K, V> *_right;
    RBTreeNode<K, V> *_parent;

    std::pair<K, V> _kv;
    Colour _col;

    RBTreeNode(const pair<K, V> &kv)
        : _left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv), _col(RED)
    {
    }
};

template <class K, class V>
class RBTree
{
    typedef RBTreeNode<K, V>  Node;

public:
    RBTree() : _root(nullptr)
    {
    }
    bool Insert(const pair<K, V> &kv)
    {
        if (_root == nullptr)
        {
            _root = new Node(kv);
            _root->_col = BLACK;
            return true;
        }
        // 找到要插入的位置
        Node *parent = nullptr;
        Node *cur = _root;

        while (cur)
        {
            if (cur->_kv.first < kv.first)
            {
                parent = cur;
                cur = cur->_right;
            }
            else if (cur->_kv.first > kv.first)
            {
                parent = cur;
                cur = cur->_left;
            }
            else
            {
                // 有重复的元素不允许插入了
                return false;
            }
        }
        cur = new Node(kv);
        cur->_col = RED;
        if (parent->_kv.first < kv.first)
        {
            parent->_right = cur;
        }
        else
        {
            parent->_left = cur;
        }
        cur->_parent = parent;
        // 调整结构
        // 父节点为黑色时不需要调整
        while (parent && parent->_col == RED)
        {
            Node *grandfather = parent->_parent;
            if (parent == grandfather->_left)
            {
                Node *uncle = grandfather->_right;
                // u存在且为红
                if (uncle && uncle->_col == RED)
                {
                    // 变色
                    parent->_col = uncle->_col = BLACK;
                    grandfather->_col = RED;
                    // 向上更新
                    cur = grandfather;
                    parent = cur->_parent;
                }
                // u不存在 或 存在且为黑
                else
                {
                    if (cur == parent->_left)
                    {
                        //     g
                        //   p
                        // c
                        // 右旋的过程为
                        // 1.父节点变为当前节点的右节点，
                        // 2.原当前节点的右节点作为父节点的左节点
                        // 3.把当前节点的父节点连接起来
                        rotateR(grandfather);
                        parent->_col = BLACK;
                        grandfather->_col = RED;
                    }
                    else
                    {
                        //     g
                        //   p
                        //		c
                        rotateL(parent);
                        rotateR(grandfather);
                        cur->_col = BLACK;
                        grandfather->_col = RED;
                    }
                    break;
                }
            }
            else//parent == grandfather->_right
            {
                Node *uncle = grandfather->_left;
                // u存在且为红
                if (uncle && uncle->_col == RED)
                {
                    // 变色
                    parent->_col = uncle->_col = BLACK;
                    grandfather->_col = RED;
                    // 向上更新
                    cur = grandfather;
                    parent = cur->_parent;
                }
                // u不存在 或 存在且为黑
                else
                {
                    if (cur == parent->_right)
                    {
                        rotateL(grandfather);
                        grandfather->_col = RED;
                        parent->_col = BLACK;
                    }
                    else
                    {
                        //     g
                        //   p
                        //		c
                        rotateR(parent);
                        rotateL(grandfather);
                        cur->_col = BLACK;
                        grandfather->_col = RED;
                    }
                    break;
                }
            }
        }
        _root->_col = BLACK;
        return true;
    }

private:
    // 1.父节点为当前节点的左节点
    // 2.当前节点的左节点为父节点的右节点
    // 3.将当前节点连接起来
    void rotateL(Node *parent)
    {
        Node*cur = parent->_right;
        Node*curleft = cur->_left;

        parent->_right = curleft;
        if(curleft)
        {
            curleft->_parent = parent;
        }

        Node* ppnode = parent->_parent;
        cur->_left = parent;
        parent->_parent = cur;

        if(ppnode == nullptr)
        {
            _root = cur;
            cur = _root;
        }
        else
        {
            if(ppnode->_left == parent)
            {
                ppnode->_left = cur;
            }
            else
            {
                ppnode->_right = cur;
            }
            cur->_parent = ppnode;
        }
    }

    void rotateR(Node *parent)
    {
        Node *cur = parent->_left;
        Node *curright = cur->_right;

        parent->_left = curright;
        if (curright)
        {
            curright->_parent = parent;
        }
        Node *ppnode = parent->_parent;
        cur->_right = parent;
        parent->_parent = cur;

        if (ppnode == nullptr)
        {
            _root = cur;
            cur->_parent = nullptr;
        }
        else
        {
            if (ppnode->_left == parent)
            {
                ppnode->_left = cur;
            }
            else
            {
                ppnode->_right = cur;
            }
        }
        cur->_parent = ppnode;
    }

private:
    Node *_root;
};